package NC40_两个链表生成相加链表;

import java.util.*;


class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val){
        this.val = val;
        this.next = null;
    }
}

public class Solution {
    /**
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if (head1 == null){
            return head2;
        }
        if (head2 == null){
            return head1;
        }
        head1 = reverse(head1);
        head2 = reverse(head2);

        ListNode newHead = add(head1, head2);
        newHead = reverse(newHead);
        return newHead;
    }

    private ListNode add(ListNode head1, ListNode head2) {
        int carry = 0;
        ListNode dummyNode = new ListNode(-1);
        ListNode cur = dummyNode;

        while (head1 != null || head2 != null){
            if (head1 != null){
                carry += head1.val;
                head1 = head1.next;
            }
            if (head2 != null){
                carry += head2.val;
                head2 = head2.next;
            }
            cur.next = new ListNode(carry % 10);
            cur = cur.next;
            carry /= 10;

        }
        if (carry != 0){
            cur.next = new ListNode(carry);
        }
        return dummyNode.next;
    }

    private ListNode reverse(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

}